/**
 * 3. Longest Substring Without Repeating Characters
 * https://leetcode.com/problems/longest-substring-without-repeating-characters/
 */
package lc3;

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        String s = "abcdba";
        int length = new Solution().lengthOfLongestSubstring(s);
        System.out.println(length);
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int length = 0;
        int lastRepeat = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                lastRepeat = Math.max(lastRepeat, map.get(c));
            }
            length = Math.max(length, i - lastRepeat);
            map.put(c, i);
        }
        return length;
    }
}

class Solution_lenchu01 {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 1) {
            return 1;
        }
        Map<Character, Integer> map = new HashMap<>();
        int length = 0;
        int offset = 0 - 1;
        int lastRepeat = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int max = 0;
            if (map.get(c) == null) {
                map.put(c, i);
                max = i - offset;
            } else {
                int lastPosition = map.get(c);
                lastPosition = lastPosition > lastRepeat ? lastPosition : lastRepeat;
                int a = i - lastPosition;
                int b = lastPosition - offset;
                max = a > b ? a : b;
                offset = lastPosition;
                map.put(c, i);
                lastRepeat = lastPosition;
            }
            length = length > max ? length : max;
        }
        return length;
    }
}
